perm filename GEOMES[0,BGB] blob
sn#107842 filedate 1974-06-26 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00015 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 TITLE PAGE & CONTENTS. AUGUST 1974
C00006 00003 1.0 INTRODUCTION TO GEOMEL, GEOMES and MESGEM.
C00010 00004 1.1 GEOMES PRIMER. Geometric Modeling Embedded in SAIL.
C00014 00005
C00017 00006 1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
C00019 00007 2.0 MEMORY, CONTROL, INPUT AND OUTPUT ROUTINES.
C00021 00008 3.0 DATUM AND LINK NAMES.
C00023 00009 4.0 WINGED EDGE PRIMITIVES.
C00027 00010 4.0 EULER MAKE PRIMITIVES.
C00029 00011 5.0 EULER KILL PRIMITIVES.
C00030 00012 6.0 EASY POLYHEDRON ROUTINES.
C00032 00013 6.0 EUCLIDEAN TRANSFORMATIONS.
C00036 00014 7.0 IMAGE FORMING ROUTINES.
C00038 00015 9.0 Description of GEOMED Source Code.
C00041 ENDMK
C⊗;
TITLE PAGE & CONTENTS. AUGUST 1974
GEOMED AS A GEOMETRIC MODELING SYSTEM.
BRUCE G. BAUMGART
ABSTRACT: The subroutines under GEOMED are presented as a modeling
system accessible from LISP, SAIL and SAIL message procedures.
_______________________________________________________________________________
1.0 Introduction to GEOMEL, GEOMES, MESGEM and CRE.
1.1 GEOMES PRIMER. Geometric Modeling Embedded in SAIL.
1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
1.3 GEOMEL PRIMER. Geometric Modeling Embedded in LISP.
1.4 CRE PRIMER. Contour Region Edge image processing.
1.5 Auxillary Programs: XIP, XAP, FILMED, BLOWUP, MKVID and DDVID.
2.0 Memory, Control, Input and Output Routines.
GEOMED MKUNIV MKNODE KLNODE
MKWORLD MKCAMERA MKWINDOW
OUTB3D OUTGEM OUTCAM OUTVID PLOTO
INB3D INGEM INCAM INCRE
3.0 Datum and Link Names:
XWC YWC ZWC AA BB CC XPP YPP ZPP
IX IY IZ JX JY JZ KX KY KZ
NFACE PFACE NED PED NVT PVT DAD SON BRO SIS
ALT ALT2 CW CCW CAR8 CDR8
4.0 Winged Edged Primitives:
MKB MKF MKE MKV MKFRAME
WING INVERT EVERT
ECW ECCW OTHER VCW VCCW FCW FCCW
BDET BATT BGET
5.0 Euler Routines:
MKBFV MKEV ESPLIT MKFE GLUEE
KLBFEV KLFE KLEV UNGLUE
GLUE MKCOPY SWEEP ROTCOM PYRAMID FVDUAL
MKCUBE MKCYLN MKBALL
BIN BUN BSUB MKCVEX
MKBUCK ECUT FCUT BCUT
6.0 Euclidean Routines:
TRANSL ROTATE SHRINK APTRAN INTRAN DISTANCE
NORM MKROT1 ORTHO1 ORTHO2 DETERM ANGL3V
7.0 Image Forming Routines:
GEODPY IIIDPY SHOW1 SHOW2 SHOW3 SHOW4
TAKE1 TAKE2 OCCULT SHADOW CLIPER
VPROJ UNPROJ FACOEF ECOEF
8.0 Arithmetic and Display Routines:
PI SQRT LOG SIN COS ATAN ATAN2 ASIN ACOS
DPYBUF DPYSST DPYSET DPYBIG DPYBRT
AVECT AIVECT RVECT RIVECT DPYOUT
9.0 Description of GEOMED Source Code.
1.0 INTRODUCTION TO GEOMEL, GEOMES and MESGEM.
GEOMED is implemented in PDP-10 machine code and is composed
of about 250 modeling subroutines. These subroutines are SAIL and
LISP accessible depending on how they are assembled and loaded. When
assembled and load for SAIL, the GEOMED subroutines are called GEOMES
for "Geometric Modeling Embedded in SAIL"; when the routines are
assembled and loaded for LISP, they are referred to as GEOMEL
standing for "Geometric Modeling Embedded in LISP".
Strictly defined, I intended to use the name "GEOMED" only
for the editor itself and to call the larger project "GEM" for
Geometric Modeling; however this has not caught on, and so the reader
is warned that the named "GEOMED" may refer to either the interactive
drawing program or to other entities including GEOMEL, GEOMES,
MESGEM, the data structures, the command languages, and so on.
As a graphics language, GEOMED is all semantics with no
syntax of its own. The subroutines take from one to four arguments,
return one or no values, and usually have considerable side effects
on the data structures. Unless otherwise noted, all arguments and
values are integers; subroutines executed only for effect tend to
return integer value zero.
The GEOMED data structure is implemented as twelve word
blocks containing pointers and data in the fashion usual to graphics
and simulation; an introduction to this technology can be found in
Knuth (volume I, chapter 2). The twelve word blocks are called
"nodes". Nodes are referred to by their actual machine address in the
user core image, which is an integer called a "link". Subroutines
that take nodes as arguments or return nodes as values pass links
rather than the nodes themselves. In SAIL, the user core image can
be accessed as a special array named MEMORY.
1.1 GEOMES PRIMER. Geometric Modeling Embedded in SAIL.
The first example GEOMES program, immediately below, creates
two cubic prisms and displays them rotating. The header file,
GEOMES.HDR, is kept on the disk area [GEM,HE] and contains the names
of the necessary load modules, the declarations of all the modeling
routines and SAIL macros for accessing GEOMED data structures. I
would strongly advise the user to study a copy of the header for it
is necessarily the most accurate index of the modeling routines.
After the header, the first routine to execute must be MKUNIV
(make universe), which initialize the modeling data structures. In
the example, two blocks are created using the MKCUBE routine which
takes three arguments: width, breadth and height of a rectangular
parallelepiped. All creation routines return an integer which is the
absolute machine address of the GEOMED node of the entity created.
(GEOMED data structures have absolutely nothing to do with LEAP).
The next routine used is GEODPY which refreshs the display of
the model using the default parameters or GEOMED. (See SHOW1 and
SHOW2 for more flexible display refresh routines). Finally, the
example calls TRANSL and ROTATE which perform the the Euclidean
transformations translation and rotation. TRANSL takes four argument:
first the thing to be moved followed by the three components of a
translation vector; similarly ROTATE takes four arguments: first the
thing to be moved followed by the three components of a rotation
vector.
-------------------------------------------------------------------------------
BEGIN "EXAMPLE1"
REQUIRE "GEOMES.HDR[GEM,HE]" SOURCE_FILE;
DEFINE π="3.1415927";
INTEGER B1,B2;
MKUNIV;
B1 ← MKCUBE(2,4,8);
B2 ← MKCUBE(1,2,4);
TRANSL(B2,-2,2,0);
WHILE TRUE DO
BEGIN
GEODPY;
ROTATE(B1,π/10,π/12,π/13);
ROTATE(B2,-π/14,π/16,-π/17);
END;
END "EXAMPLE1";
-------------------------------------------------------------------------------
Now read Example #2, immediately below. In this example the
model of the yellow arm is read in and the first three joints are run
through a simulated arm motion. The routine INB3D reads B3D
polyhedra files. The FDNAME, find name, routine searchs for GEOMED
body print names, FDNAME returns zero when a name is not found. The
routine INCAM reads in a camera file. Finally, the routine SHOW2
calls the hidden line eliminator; leaving the SHOW2 arguments zero
causes default parameters to be used.
-------------------------------------------------------------------------------
BEGIN "EXAMPLE2"
REQUIRE "GEOMES.HDR" SOURCE_FILE;
DEFINE α="COMMENT";
INTEGER B1,B2,J1,J2,J3,J4,J5,J6,C1,CHR,I;
MKUNIV;GEODPY;
B1 ← INB3D("ARM[DAT,BGB]"); α MODEL OF THE YELLOW ARM;
B2 ← INB3D("TABLE[DAT,BGB]"); α MODEL OF THE HAND/EYE TABLE;
J1 ← FDNAME("JOINT1"); α SHOULDER - ABOUT VERTICAL;
J2 ← FDNAME("JOINT2"); α ARM - ABOUT HORIZONTAL;
J3 ← FDNAME("JOINT3"); α SLIDE;
J4 ← FDNAME("JOINT4"); α WRIST TWIST;
J5 ← FDNAME("JOINT5"); α WRIST FLAP;
J6 ← FDNAME("JOINT6"); α HAND
C1 ← INCAM("ARMCAM[DAT,BGB]");
SHOW2(0,0); α HIDDEN LINE ELIMINATION;
FOR I←0 THRU 70 DO
BEGIN
ROTATE(-J1,0,0,π/18);
ROTATE(-J2,0,0,π/20);
TRANSL(-J3,0,0,0.1);
SHOW2(0,0);
END;
END "EXAMPLE2"
-------------------------------------------------------------------------------
1.2 MESGEM PRIMER. Message Procedure Geometric Modeling.
The message procedure modeling routines are declared by the
source file MESGEM.HDR[GEM,HE] which should be used in place of
GEOMES.HDR[GEM,HE]. Almost all the subroutine and link names of
MESGEM are the same as in GEOMES, however the user will have to load
his program with GLBLOW from SYS.
1.3 GEOMEL PRIMER. Geometric Modeling Embedded in LISP.
A dump version of GEOMEL is available on [GEM,HE] and the
LISP is a current version UCI LISP.
1.4 CRE PRIMER. Contour Region Edge image processing.
1.5 Auxillary Programs: XIP, XAP, DDVID, BLOWUP & CINEMA.
XIP and XAP are explained somewhat by the document XAP.BGB[UP,DOC].
2.0 MEMORY, CONTROL, INPUT AND OUTPUT ROUTINES.
top of stack ← GEOMED; Geometric Editor.
univer ← MKUNIV; Make universe, initialization.
node ← MKNODE(word0); Make node with given type bits.
KLNODE(QNODE); Kill node.
The routine named GEOMED, passes control to the geometric
editor, which enters the jump table command scanner described in the
A.I. memo #232. When the exit command "εE" is given, GEOMED returns
the the address of the node which is at the top of its stack (or
zero, if the stack is empty). MKUNIV; initializes GEOMED node
space. QNODE ← MKNODE(Q); takes a node from the empty node list;
memory space is requested from SAIL or LISP as needed. The integer Q
is stored in the TYPE bits (word zero) of the newly created node.
KLNODE(QNODE); returns a node to the empty node list.
The following routines
OUTB3D(filename,BODY);
OUTGEM(filename,BODY);
OUTCAM(filename);
OUTV2D(filename);
body ← INB3D(filename);
body ← INGEM(filename);
camr ← INCAM(filename);
body ← INCRE(filename);
3.0 DATUM AND LINK NAMES.
Datum names: XWC YWC ZWC World Coordinates Locus.
XPP YPP ZPP Perspective Projected Locus.
AA BB CC KK Face or Edge Coefficients.
IX IY IZ I-unit vector of a frame.
JX JY JZ J-unit vector of a frame.
KX KY KZ K-unit vector of a frame.
The above datum names all refer to real numbers. In GEOMES,
the datum names are defined as MEMORY array references and so can
appear on the left of a left arrow. In GEOMEL, eighteen
corresponding datum store routines are provided; for example:
XWC.(Xvalue,Vertex), will store a new X coordinate value into a
vertex node.
Link names: NFACE PFACE Face Ring.
NED PED Edge Ring.
NVT PVT Vertex Ring.
DAD SON Parts Tree Links.
BRO SIS Parts Tree Links.
ALT ALT2 GEOMED Temporaries.
CW CCW Body ring of world.
CAR8 CDR8 User Links.
In both GEOMES and GEOMEL, the links may be modified by the
two argument subroutines of the same name with a period "." suffixed
to it for LISP or a dollar sign suffixed for SAIL. For example,
ALT$(Q,E) will place the link (or integer value) Q into the ALT
halfword link position of the node E.
4.0 WINGED EDGE PRIMITIVES.
4.1 NODE MAKERS.
body ← MKB(world or 0)
face ← MKF(body)
edge ← MKE(body)
vertex ← MKV(body)
frame ← MKFRAME;
MKB makes a body node and place it in the body ring of the
given world (or in the now world if the given world argument is
zero). MKF, MKE and MKV make a face, edge or vertex node respectively
and place it in the proper given body's face, edge or vertex ring.
MKFRAME simply returns a frame node with a unit rotation matrix and
zero world locus.
4.2 WING LINK MUNGING.
WING(edge1,edge2);
INVERT(edge);
EVERT(body);
Given that each edge has its proper two vertices and two
faces, WING(E1,E2) will make the edges point at each other in the
correct orientation. INVERT(edge) will flip the linear orientation of
an edge. EVERT(body) will flip the surface orientation of a body,
making solids into holes and vise versa.
4.3 FACE AND VERTEX PERIMETER ACCESSING.
next cw edge ← ECW(edge,face or vertex);
next ccw edge ← ECCW(edge,face or vertex);
cw vertex ← VCW(edge,face);
ccw vertex ← VCCW(edge,face);
cw face ← FCW(edge,vertex);
ccw face ← FCCW(edge,vertex);
face or vertex ← OTHER(edge,face or vertex);
ECW(E,FV) and ECCW(E,FV) fetch the next edge clockwise or
counter clockwise from the given edge about the given face or vertex.
VCW(edge,face) and VCCW(edge,face) fetch the next vertex clockwise or
counter clockwise from the given edge with repect to the given face.
FCW(edge,vertex) and FCCW(edge,vertex) fetch the next face clockwise
or counter clockwise from the given edge with repect to the given
vertex. The OTHER(<edge>,<face|vertex>) will fetch the face or vertex
of the given edge which is not equal to the given face or vertex.
4.3 PARTS TREE AND BODY GET.
BDET(body);
BATT(body1,body2);
body ← BGET(face or edge or vertex);
BDET(body) will detach a body from the parts tree.
4.0 EULER MAKE PRIMITIVES.
4.1 BNEW ← MKBFV; Make vertex polyhedron.
4.2 VNEW ← MKEV(F,V); MAKES NEW EDGE AND VERTEX SUCH THAT:
VNEW = NVT(ENEW); V = PVT(ENEW);
VNEW ← ESPLIT(E); MAKES NEW EDGE AND VERTEX...
4.3 ENEW ← MKFE(V1,F,V2); MAKES NEW FACE AND EDGE SUCH THAT:
FNEW = NFACE(ENEW); F = PFACE(ENEW);
V1 = PVT(ENEW); V2 = NVT(ENEW).
4.4 ENEW ← GLUEE(F1,V1,F2,V2); MAKES NEW EDGE, KILLS F2,
AND MAKES A HOLE OR KILLS A BODY.
V1 = PVT(ENEW); V2 = NVT(ENEW).
4.2 VNEW ← MKEV(FACE,VERTEX);
VNEW ← ESPLIT(EDGE);
Make a new edge and a new vertex in the given FACE from the
given VERTEX; the new vertex is return, VNEW; the new edge can be
accessed by taking PED(VNEW).
ESPLIT, makes a new edge and a new vertex, VNEW; the new edge may be
obtained by taking PED(VNEW); the new edge is place between VNEW and
PVT(EDGE).
4.3 ENEW ← MKFE(V1,FACE,V2);
Make a new face and a new edge by joining V1 and V2 of FACE.
The new edge is returned, ENEW; the new face may always be obtained
by taking NFACE(ENEW).
5.0 EULER KILL PRIMITIVES.
5.1 QNEW ← KLBFEV(Q); Kill entity.
5.2 F ← KLFE(E); Kill E and NFACE(E), return PFACE(E).
5.3 E ← KLEV(V); Kill V and PED(V), return other E of V.
V ← KLEV(E); Kill E and NVT(E), retirn PVT(E).
5.4 FNEW ← UNGLUE(E); Undo an GLUEE.
.....................................................................
6.0 EASY POLYHEDRON ROUTINES.
body ← GLUE(face1,face2); Glue face-face.
qnew ← MKCOPY(entity); Make copy.
face ← SWEEP(face,flag); Sweep cylinder.
face ← ROTCOM(face); Rotation completion.
peak ← PYRAMID(fv); Make pyramid on a face (or vertex).
body ← FVDUAL(body); Make face/vertex dual of a body.
bnew ← MKCUBE(dx,dy,dz); Make right rectangular prism.
bnew ← MKCYLN(radius,n,dz); Make right cylinder.
bnew ← MKBALL(radius,m,n; Make sphere approximation.
MKCUBE(dx,dy,dz) creates and returns a cubic right prism.
MKCYLN(r,n,z) creates and returns a regular N-sided right prism.
bnew ← BIN(body1,body2); Body intersection.
bnew ← BUN(body1,body2); Body union.
bnew ← BSUB(body1,body2); Body subtraction.
MKCVEX(body or face); Make convex faces.
6.0 EUCLIDEAN TRANSFORMATIONS.
Euclidean Transformations with respect to world frame:
TRANSL(object,dx,dy,dz);
ROTATE(object,wx,wy,wz);
SHRINK(object,sx,sy,sz);
Euclidean Transformations with respect to objects own frame:
TRANSL(-object,dx,dy,dz);
ROTATE(-object,wx,wy,wz);
SHRINK(-object,sx,sy,sz);
Euclidean Transformations with respect to arbitrary frame:
TRANSL(XWD(frame,object),dx,dy,dz);
ROTATE(XWD(frame,object),wx,wy,wz);
SHRINK(XWD(frame,object),sx,sy,sZ);
Make Euclidean Transformation
tran ← TRANSL(0,dx,dy,dz);
tran ← ROTATE(0,wx,wy,wz);
tran ← SHRINK(0,sx,sy,sz);
OBJECT ← APTRAN(OBJECT,TRAN);
FRAME ← INTRAN(FRAME);
Z ← DISTANCE(BFEV1,BFEV2);
NORM
MKROT1
ORTHO1(FRAME)
ORTHO2(FRAME)
Z ← DETERM(FRAME)
ANGL3V(V1,V2,V3)
7.0 EUCLIDEAN TRANSFORMATIONS.
When the ENTITY argument is non-zero, these subroutines
perform the indicated Euclidean Transformation: translation,
rotation, dilation and reflection. When the ENTITY argument is ZERO,
then a FRAME node representing the desired transformation is
returned.
FRAMES and EUCLIDEAN TRANSFORMATIONS
A frame node has two intrepretations: it may be used to
represent a frame of reference or it may be used to specify a
Euclidean transformation.
As a frame of reference the XWC, YWC, ZWC datums contain the
location of the origin of the frame in world coordinates; and the
remaining nine datums IX,IY,IZ, JX,JY,JZ, KX,KY,KZ are the components
of three unit vectors I, J, and K that determine a right handed
rectangular Cartesian coordinate system. The nine components of the
unit vectors form an orthonormal rotation matrix.
As a Euclidean transformation, the frame is applied to the
3-D world coordinates of an entity Q to make new coordinates.
---------------------------------------------------------------------
| APTRAN's inner most subroutine. |
| Expects arguments in V and Q. Clobbers 1,2,X,Y,Z. |
| |
| X ← XWC(V); |
| Y ← YWC(V); |
| Z ← ZWC(V); |
| |
| XWC(V) ← X*IX(Q) + Y*JX(Q) + Z*KX(Q) + XWC(Q); |
| YWC(V) ← X*IY(Q) + Y*JY(Q) + Z*KZ(Q) + YWC(Q); |
| ZWC(V) ← X*IZ(Q) + Y*JZ(Q) + Z*KZ(Q) + ZWC(Q); |
---------------------------------------------------------------------
HOMOGENEOUS COORDINATES (LACK OF...)
The interpretation of frame nodes can be given in the
four by four notation of homogeneous coordinates.
7.0 IMAGE FORMING ROUTINES.
GEODPY; GEOMED's display refresh.
SHOW1(window,glass); Display all edges.
SHOW2(window,glass); Display visible edges only.
SHOW3(window,glass); Display all visible faces.
8.0 ARITHMETIC AND DISPLAY ROUTINES.
SQRT LOG SIN COS ATAN ATAN2 ASIN ACOS PI
DPYSET DPYBIG DPYBRT DPYSST
AVECT AIVECT RVECT RIVECT DPYOUT
The usual arithmetic and display routines used at Stanford
are embedded in GEOMED; so that the typical user should not require
SAITRG or DISPLY or any of their equivalents. The next paragraph is a
short explanation of the display functions, which are similar to
those document in DISPLY.RBN[UP,DOC]@SAIL.
The CRT display screens are refreshed by a special purpose
display computer which executes a display file from core memory. With
the exception of DPYSET and DPYOUT; all of the diaplay subroutines
add display code to the display file. The display screen has 1024 by
1024 visible addressible positions with the origin in the center of
the screen, the positive X-axis to the right and the positive Y-axis
upwards. Thus display coordinates may range from -512 to +511;
9.0 Description of GEOMED Source Code.
The overall structure of GEOMED is determined by the urge to
have approximately one subroutine per page of source code. The
subroutine calling conventions are SAIL like; accumulator 17 (17
octal of course !) is named "P" and is used as a pushdown list for
arguments and return addresses. The subroutine calling sequence goes:
PUSH P,ARG↔ PUSH P,ARG↔ ... PUSHJ P,SUBR and a subroutine return must
fix up the stack SUB P,[XWD N+1,N+1] and JRST @N+1(P).
The somewhat unusal appearance of GEOMED machine code arises
from the use of FAIL assembler macros to implement ALGOL like
subroutine notation and KNUTH like datum/link notation; and from the
use of double-arrow "↔" to place more than one machine instruction
per line and the use of seven alternate PDP-10 mnemonics.
The seven alternate PDP-10 mnemonics are LAC, DAC, CAR, CDR,
DIP, DAP and GO for MOVE, MOVEM, HLRZ, HRRZ, HRLM, HRRM and JRST
respectively. The LAC, DAC, DIP, DAP come from PDP-1 nomensclature
and are shorter and more pronoucible than their PDP-10 equivalents.
The CAR and CDR are from LISP which got them from the IBM-709. The
GO comes from ALGOL and is shorter and more descriptive than JRST.
The PDP-10 op code names sacrifice pronoucibility for systematic
nomensclature; and although I once proposed having alternate concise
euphonious names for the most frequently used operations; the idea
was quite unpopular and so I have abandoned it for all except the
above seven mnemonics.